# leetcode 106 从中序遍历和后序遍历序列构造二叉树

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:

        def build(__in, __post):
            if len(__post) == 0:
                return None
            root_value = __post[-1]  # 根节点一定是后序遍历中，最后一项
            root = TreeNode(val=root_value) # 先用后序遍历的结果构建出根节点
            # 然后找到根节点在中序遍历中的位置
            # 中序遍历结果中，根节点左边的为左子树，根节点右边的为右子树
            root_index = __in.index(root_value)
            # 通过根节点位置分割中序遍历中的左右子树
            __in_left = __in[:root_index]
            __in_right = __in[root_index + 1:]

            # 在后序遍历中的左右子树，和中序遍历的左右子树是相等的
            # 因此只需要知道左子树的长度，就可以分割出左子树
            __post_left =__post[:len(__in_left)]

            # 右子树为后序遍历中，去除最后一项根节点，以及左子树部分，剩余的部分
            __post_right = __post[len(__in_left): -1]

            # 然后递归构造左右子树
            # 左子树通过子左中序和子左后序构造
            # 右子树通过子右中序和子右后序构造
            root.left = build(__in_left, __post_left)
            root.right = build(__in_right, __post_right)

            # 构造完毕返回根节点
            return root
        root = build(inorder, postorder)
        return root

